#
# @lc app=leetcode.cn id=887 lang=python3
#
# [887] 鸡蛋掉落
#


# @lc code=start
class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        memo = {(k, 1): 1}

        def dp(k, T):
            if T == 1:
                return 1
            if k == 1:
                return T

            memo[(k - 1, T - 1)] = dp(k - 1, T - 1)
            return 1 + memo[(k - 1, T - 1)] + memo[(k, T - 1)]

        T = 1
        while memo[(k, T)] < n:
            T += 1
            memo[(k, T)] = dp(k, T)
        return T


# @lc code=end
